/*
 * @lc app=leetcode.cn id=220 lang=javascript
 *
 * [220] 存在重复元素 III
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} t
 * @return {boolean}
 */

/**
 * 对nums遍历，并按照每个桶t+1的大小放到不同的桶中
 * 存在nums[i]时，如果桶中已经存在元素，则这两个元素满足条件
 * 如果为空桶，则判断和num[i]相邻的桶中的元素（每个桶中只会有一个元素）是否满足条件
 */

var getInd = function(num, t){
  return Math.floor(num / (t + 1))
}

var containsNearbyAlmostDuplicate = function (nums, k, t) {
  let buckets = new Map(); // 因为每个桶只会有一个元素，所以用map就可以
  for (let i = 0; i < nums.length; i++) {
    // 计算桶序号，下取整
    let ind = getInd(nums[i], t); 
    if(buckets.has(ind)) return true;
    if(buckets.has(ind - 1) && Math.abs((buckets.get(ind - 1) - nums[i])) <= t) return true;
    if(buckets.has(ind + 1) && Math.abs((buckets.get(ind + 1) - nums[i])) <= t) return true;
    buckets.set(ind, nums[i]);
    if(i >= k) {
      let preInd = getInd(nums[i - k], t);
      buckets.delete(preInd);
    }
  }
  return false;
};
// @lc code=end

